package com.gitee.feizns.explore.data_structure.tree.bs.mid;

/**
 * 889. 根据前序和后序遍历构造二叉树
 * @author feizns
 * @since 2020/3/14
 */
public class ConstructFromPrePost {

    public static void main(String[] args) {
        TreeNode node = new ConstructFromPrePost().constructFromPrePost(new int[]{1,2,4,5,3,6,7}, new int[]{4,5,2,6,7,3,1});
        System.out.println(node);
    }

    int[] pre;
    int[] post;

    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        this.pre = pre;
        this.post = post;
        return buildTree(0, pre.length - 1, 0, post.length - 1);
    }

    public TreeNode buildTree(int pl, int pr, int tl, int tr) {
        TreeNode ret = null;
        if ( pl == pr )
            ret = new TreeNode(pre[pl]);
        else if ( pl < pr ) {
            ret = new TreeNode(pre[pl]);
            if ( pre[pl + 1] == post[tr - 1] ) {
                ret.left = buildTree(pl + 1, pr, tl, tr - 1);
            } else {
                int i = index(pre, post[tr - 1], pl + 1, pr);
                int j = index(post, pre[pl + 1], tl, tr - 1);
                ret.left = buildTree(pl + 1, i - 1, tl, j);
                ret.right = buildTree(i, pr, j + 1, tr - 1);
            }
        }
        return ret;
    }

    private static int index(int[] arr, int val, int start, int end) {
        for (int i = start; i <= end; i++) {
            if ( arr[i] == val )
                return i;
        }
        return -1;
    }

}
